package leetcode;


import javax.swing.tree.TreeNode;
import java.util.*;

public class LeetCode820 {

    //当前字符串比原来的长 有子串则更新并删除短串
    //当前字符串比原来的短 当前字符是子串则跳过
    //否则更新到字典中
    //超出限制
    public int minimumLengthEncoding1(String[] words) {
        List<String> list = new ArrayList<>();
        list.add(words[0]);
        for (int i = 0; i < words.length; i++) {
            int length = words[i].length();
            for (int j = 0; j < list.size(); j++) {
                String s = list.get(j);
                int length1 = s.length();
                if (length > length1 && words[i].substring(length - length1).equals(s)) {
                    list.remove(j);
                    list.add(words[i]);
                } else if (length <= length1 && s.substring(length1 - length).equals(words[i])) {
                    continue;
                } else {
                    list.add(words[i]);
                }
            }
        }
        int count = 0;
        for (String s : list) {
            count += s.length();
        }
        return count + list.size();
    }

    //------------------------------------------------------------------
    //关键条件判断是不是后缀，前缀和中缀都不可以
    //多读题 很多隐藏信息没用上
    //后缀表达式很重要 重点理解后缀表达式

    //减法思想！！！！
    public int minimumLengthEncoding2(String[] words) {
        Set<String> good = new HashSet(Arrays.asList(words));
        for (String word : words) {
            for (int k = 1; k < word.length(); ++k)
                good.remove(word.substring(k));
        }

        int ans = 0;
        for (String word : good)
            ans += word.length() + 1;
        return ans;
    }

    public static void main(String[] args) {
        LeetCode820 leetCode820 = new LeetCode820();
        leetCode820.minimumLengthEncoding(new String[]{"time", "me", "bell"});
    }

    public int minimumLengthEncoding5(String[] words) {
        //a-z
        TreeNode root = new TreeNode(0), tmp = root;
        for (String word : words) {
            tmp = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                int index = word.charAt(i) - 'a';
                TreeNode treeNode = tmp.node[index];
                if (treeNode == null) {
                    tmp.node[index] = new TreeNode(word.length() - i);
                }
                tmp = tmp.node[index];
            }
        }
        System.out.println(Arrays.toString(root.node));
        //开始遍历这棵树 寻找每个节点的最长长度 是一个26叉树
        getTreeDeep(root, 0);
        return result + count;
    }

    private int result = 0;

    private int count = 0;

    public int minimumLengthEncoding(String[] words) {

        //a-z
        TreeNode root = new TreeNode(0), tmp = root;
        for (String word : words) {
            tmp = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                int index = word.charAt(i) - 'a';
                TreeNode treeNode = tmp.node[index];
                if (treeNode == null) {
                    tmp.node[index] = new TreeNode(word.length() - i);
                }
                tmp = tmp.node[index];
            }
        }
        return result + count;
    }


    private void getTreeDeep(TreeNode tmp, int deep) {
        int childCount = 0;
        for (int i = 0; i < tmp.node.length; i++) {
            if (tmp.node[i] != null) {
                childCount++;
                getTreeDeep(tmp.node[i], deep + 1);
            }
        }
        //没有子节点
        if (childCount == 0) {
            result += deep;
            count++;
        }
    }


    class TreeNode {
        TreeNode[] node = new TreeNode[26];
        int deep;
        //记录孩子节点个数

        public TreeNode(int deep) {
            this.deep = deep;
        }
    }
}
